package io.gitee.wiqer.medium;

import org.junit.Test;

public class SolutionNC105_Search {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if(nums==null||nums.length == 0)return -1;
        return search(nums,0,nums.length-1,target);
    }
    public int search (int[] nums,int start,int end, int target) {
        // write code here
        if (target<nums[start]||target > nums[end]) {
            return -1;
        }else if (target==nums[start]){
            return start;
        }else if (end-start<2){
            if (target==nums[end]) {
                return end;
            }
            return -1;
        }
        int width= end-start;
        if(nums[width/2+start]>=target){
           return search(nums,start+1,width/2+start,target);
        } else {
           return search(nums,width/2+start,end,target);
        }
    }
    @Test
    public void test(){
        int[] nums={1,2,4,4,5};
        System.out.println(search(nums,4)) ;
        System.out.println(search(nums,3)) ;
        int[] nums3={1,1,1,1,1};
        System.out.println(search(nums3,1)) ;
        int[] nums4={1,2,2,3,4};
        System.out.println(search(nums4,2)) ;
        int[] nums5={2,4,6,6,7,7,7,7,8,17,17,18,18,20,20,22,22,23,24,25,26,27,29,29,30,31,33,34,35,35,36,36,38,38,40,41,42,43,48,48,50,52,54,54,54,56,57,58,60,60,61,61,62,62,62,62,66,67,68,71,72,73,74,75,75,78,79,79,80,80,80,81,81,82,82,82,83,84,87,87,88,89,90,90,91,92,92,94,94,97,97,98,99,100,102,102,102,104,104,105,108,110,110,110,110,113,114,115,116,117,117,118,118,120,120,120,123,123,124,125,126,127,127,128,128,128,129,130,131,131,132,133,135,136,136,139,139,146,147,148,148,148,152,152,153,155,156,156,156,156,157,159,159,160,162,163,164,165,166,166,167,167,172,172,174,174,174,175,175,177,178,178,180,180,182,183,184,184,186,188,189,191,191,191,194,195,196,197,199,200,201,201,201,202,202,203,204,205,207,207,207,208,208,208,210,211,212,213,213,214,214,215,215,218,220,221,221,222,223,224,226,226,227,229,230,231,233,234,234,235,235,237,240,240,241,241,243,243,243,244,244,245,246,249,250,253,254,255,255,257,257,257,257,258,258,258,258,261,261,264,266,266,267,268,273,273,273,274,276,280,282,284,284,291,292,293,296,297,297,298,299,300,300,301,301,303,304,305,308,308,311,312,317,317,318,320,320,322,323,326,326,326,327,327,330,331,332,333,333,333,334,335,335,336,336,338,338,338,339,339,340,341,341,342,343,343,344,345,345,347,348,349,349,350,351,355,356,357,359,361,362,362,364,364,364,365,366,367,368,369,372,373,374,374,376,378,378,379,380,381,382,383,383,384,385,386,388,388,388,389,390,391,394,395,396,396,397,397,397,397,398,399,401,404,404,405,407,407,407,410,411,412,412,413,414,414,414,415,415,415,421,422,424,425,426,429,429,430,431,432,432,434,435,435,435,436,437,439,439,439,439,442,442,442,442,442,443,443,443,444,444,445,446,446,447,447,448,448,449,449,451,452,452,453,453,454,461,462,463,465,465,465,465,470,471,471,472,473,474,474,474,475,477,479,480,480,481,482,483,484,485,487,488,489,491,491,492,494,495,496,496,496,498,503,503,505,506,508,509,510,511,511,511,513,513,514,514,516,518,518,521,522,522,522,525,525,530,530,530,530,531,531,532,533,533,533,533,534,534,536,536,537,537,539,541,541,542,544,545,547,547,550,550,551,552,553,554,554,554,555,555,556,559,559,562,562,563,564,564,565,565,566,567,567,567,569,570,570,571,572,573,573,574,574,575,579,580,580,581,581,581,582,584,584,584,585,586,587,588,591,591,593,593,593,594,594,595,596,596,597,598,598,598,600,600,600,601,602,602,602,603,603,605,605,607,608,609,610,612,613,614,614,614,615,616,618,619,619,620,620,620,623,623,623,625,625,627,628,629,630,630,631,632,633,634,634,637,638,638,638,641,642,642,643,643,645,646,646,647,649,649,650,650,651,652,653,654,654,654,655,655,656,657,657,657,658,660,663,664,665,666,666,666,667,668,669,669,669,670,672,673,674,674,674,676,676,677,677,678,681,683,685,687,687,688,690,691,691,692,694,698,701,702,705,709,711,712,713,713,713,714,714,715,715,715,716,716,716,717,717,717,718,719,719,720,720,723,724,725,725,725,726,726,728,729,733,733,735,735,736,737,740,742,742,743,744,745,747,747,748,748,749,749,750,751,751,751,754,754,754,756,757,758,758,758,760,760,763,763,764,764,766,766,768,771,771,773,773,773,773,774,774,775,775,776,777,778,780,782,783,784,788,788,789,793,796,796,796,798,798,799,799,801,801,803,803,808,808,811,812,812,813,813,814,815,815,816,819,819,820,821,824,824,825,826,826,827,831,831,832,834,834,835,835,837,838,839,847,848,849,849,850,851,851,852,852,853,853,854,854,855,855,855,856,856,859,860,862,863,863,863,866,867,867,867,871,871,873,874,874,875,875,876,876,878,880,881,881,882,884,884,884,886,887,888,888,889,890,890,892,892,892,894,896,896,897,897,899,900,901,901,902,902,902,904,905,906,906,906,906,907,908,908,908,908,914,915,916,916,916,916,918,919,920,921,921,922,923,926,926,928,930,933,937,937,940,942,942,942,942,944,944,948,948,949,949,951,952,954,954,958,959,959,960,961,962,964,965,966,967,967,968,968,968,970,971,971,972,972,973,975,976,980,981,981,981,981,981,981,982,982,982,983,984,985,985,986,986,987,987,988,989,989,990,993,994,996,997,999,999};
        System.out.println(search(nums5,999)) ;
    }
}
